BM2 链表内指定区间反转

BM2 链表内指定区间反转

使用虚拟头节点，即在头节点前面再添加一个节点

• 要反转局部链表，可以将该 局部部分当作完整链表 进行反转
• 再将已经反转好的局部链表与其他节点建立连接，重构链表

使用虚拟头节点的技巧，可以避免对头节点复杂的分类考虑，简化操作。

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

func reverseBetween( head *ListNode ,  m int ,  n int ) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    dummy := new(ListNode)
    dummy.Next = head
    pre := dummy
    // 先遍历 m
    for i := 0; i < m-1; i++ {
        // 加上虚拟头，取得 m 的前一个节点
        pre = pre.Next
    }
    
    start := pre.Next
    end := pre.Next

    // 取得子链的末尾
    for i := m; i < n; i++ {
        end = end.Next
    }
    tmp := end.Next
    
    // 切断子链的链接
    end.Next = nil
    pre.Next = reverse(start)
    start.Next = tmp
    return dummy.Next
}

func reverse(head *ListNode) *ListNode {
    pre := new(ListNode)
    for head != nil {
        tmp := head.Next
        head.Next = pre
        pre = head
        head = tmp
    }
    return pre
}